#include <stdio.h>
#include <malloc.h>
struct node {
int info;
struct node * next;
} *front , *rear;

void input(int val)
{ struct node *ptr;
ptr=(struct node*)malloc(sizeof(struct node));
	ptr->next=NULL;
	ptr->info=val;
	if (front==NULL||rear==NULL)
	{
		front=ptr;
		rear=ptr;
	}
	else 
	{
		rear->next=ptr;
		rear=ptr;
	}
}

		


void display()
{       printf("The list is\n");
	struct node *x=front;  
	while(x!=NULL)
	{
	printf("%d ",x->info);
	x=x->next;
	}
}

void insert(struct node *p,int pos,int val)
{       struct node *temp;
	temp=(struct node* )malloc(sizeof(struct node));       
	temp->info=val;	
	temp->next=NULL;
	int count=1;	
	for(;p!=NULL;p=p->next)
	{count=count+1;
	if(pos==count)
	{temp->next=p->next;
	p->next=temp;}
        }
}

void removex(struct node *p, int val)
{	for(;p!=NULL;p=p->next)
	{ if(p->info==val)
		{if(p==front)
		{struct node * temp = front;
		 front=front->next;
		 free(temp);}
		 
		 else
		 {struct node * temp = p->next;
    		 p->info = p->next->info;
    		 p->next = temp->next;
    		 free(temp);
	         }}
	}
}

int pop (struct node*p , int pos)
{  	int count=0;	
	for(;p!=NULL;p=p->next)
	{count=count+1;
	if(pos+1==count)
	{if(p==front)
		{struct node * temp = front;
		 front=front->next;
		 return temp->info;	 
		 free(temp);}
		 
		 else
		 {struct node * temp = p->next;
    		 p->info = p->next->info;
    		 p->next = temp->next;
    		 return temp->info;
		 free(temp);
	         }}
	}


}

void indexx(struct node *p , int val)
{	int index=-1;
	for(;p!=NULL;p=p->next)
	{index=index+1;
	 if(p->info==val)
	 break;
	}
	printf("index of the no is %d\n",index);
}

void count (struct node *p , int val)
{	int count=0;
	for(;p!=NULL;p=p->next)
	{if(p->info==val)
	 count=count+1;}
	printf("the no counts of the no is %d\n",count);
} 
	
void sort ()
{	
	struct node *a = NULL;
	struct node *b = NULL; 
	struct node *c = NULL;
	struct node *e = NULL; 
	struct node *tmp = NULL; 

	while(e != front->next) 
	{
		c = a = front;
		b = a->next;
		while(a != e) 
		{
		if(a->info > b->info) 
		{
		if(a == front) 
		{
		tmp = b -> next;
		b->next = a;
		a->next = tmp;
		front = b;
		c = b;
		} else {
		tmp = b->next;	
		b->next = a;
		a->next = tmp;
		c->next = b;
		c = b;
		}
		} else 
		{
		c = a;
		a = a->next;
		}
		b = a->next;
		if(b == e)
		e = a;
		}
	}
}

void reverse ()
{
struct node *temp=NULL; 
struct node *p=front;
struct node *o=NULL;
while (p!=NULL)
	{
	temp=p->next;
	p->next=o;
	o=p;
	p=temp;
	}
front=p;
front=rear;
rear=p;
}

int main()

{	int pos,i=1;
	int number,retval;
	int element,opt,x,j=0;
	char ch;
	
	do 
	{ printf("Please enter element %d \n",i);		
	scanf("%d", &element);
	input(element);
	printf("do u want to contniue\n");	
	scanf("%s",&ch);
	i=i+1;
	}while(ch!='n');
	printf("what do u want to do now \n 0.exit \n  1.append\n 2. extend \n 3.insert\n 4. remove \n 5.pop\n 6. index \n 7.count\n 8. sort \n 9.reverse\t");
	scanf("%d",&opt);
	do
{	
	switch ( opt)
	{ case  1: printf("enter the no you want to append at the end of the list");
		   scanf("%d",&x);
		   input(x);
		   display();
		   break;
	  case  2: printf("enter the size of the link list u want  to append at the end");
		   scanf("%d",&number);
		   for(j=0;j<number;j++)
		   {printf("enter the no you want to append at the end of the list");
		   scanf("%d",&x);
		   input(x);
		   }
		   display();
		   break;
	  case  3: printf("enter the no you want to insert\n");
		   scanf("%d",&x);
		   printf("enter the position at which you want to insert\n");
		   scanf("%d",&pos);
		   insert(front,pos,x);
		   display();
		   break;
	  case  4: printf("enter the no you want to remove from  the list\n");
		   scanf("%d",&x);
		   removex(front,x);
		   display();
		   break;
	  case  5: printf("enter the index at which  you want to pop");
		   scanf("%d",&x);
		   retval=pop(front,x);
		   
		   display();
		   break;
	  case  6: printf("enter the no whose index you want");
		   scanf("%d",&x);
		   indexx(front,x);
		   break;
	  case  7: printf("enter the no whose no. of occurences you want");
		   scanf("%d",&x);
		   count(front,x);
		   break;
	  case  8: sort();
		   display();
		   break;
	  case  9: reverse();
		   display();
		   break;
	  default : printf("enter a legitimate option\n");
	  }
	printf("what do u want to do now \n 0.exit \n  1.append\n 2. extend \n 3.insert\n 4. remove \n 5.pop\n 6. index \n 7.count\n 8. sort \n 9.reverse\t");
	scanf("%d",&opt);
}while(opt!=0);
}     

